#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<set>
#include<stdlib.h>
#include<time.h>
#include<map>
using namespace std;

class RandomizedSet {
public:
    /** Initialize your data structure here. */
    RandomizedSet() {
        srand((unsigned)time(NULL));
    }
    
    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    bool insert(int val) {
        if(M[val].empty()){
            V.push_back(val);
            
            M[val].push_back(i++);
            return true;
        }
        return false;
    }
    
    /** Removes a value from the set. Returns true if the set contained the specified element. */
    bool remove(int val) {
        if(M[val].empty()){
            return false;
        }
        int index = M[val].back();
        M[val].pop_back();


        V[index] = INT16_MAX;
        return true;
    }
    
    /** Get a random element from the set. */
    int getRandom() {
        vector<int> temp;
        for(auto i = M.begin();i!=M.end();++i){
            for(int t:i->second){
                temp.push_back(t);
            }
        }
        
        int index = rand()%temp.size();
        return V[temp[index]];

    }
public:
    map<int,vector<int>> M;
    vector<int> V;
    int i = 0;
    
};

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * RandomizedSet* obj = new RandomizedSet();
 * bool param_1 = obj->insert(val);
 * bool param_2 = obj->remove(val);
 * int param_3 = obj->getRandom();
 */

int main(){
    RandomizedSet randomSet;
    cout<<randomSet.insert(0)<<endl;
    cout<<randomSet.insert(1)<<endl;
    // cout<<randomSet.remove(0)<<endl;
    cout<<randomSet.insert(2)<<endl;
    cout<<randomSet.getRandom()<<endl;
    cout<<randomSet.getRandom()<<endl;
    cout<<randomSet.getRandom()<<endl;
    cout<<randomSet.getRandom()<<endl;
}